package leetcode_core.leetcode_1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 中序遍历的解法
 */
public class Codec3 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    private static final String SEP =",";
    private static final String NULL = "#";
    private StringBuilder sb;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        //层级遍历
        if(root == null){
            return "";
        }
        sb = new StringBuilder();
        //初始化队列,root入队,开始BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode head = queue.poll();
            if(head == null){
                sb.append(NULL).append(SEP);
                continue;
            }
            sb.append(head.val).append(SEP);
            //检查队头元素,由于是需要记录空节点,所以我们需要将空节点给入队
            queue.offer(head.left);
            queue.offer(head.right);
        }
        return sb.toString();
    }

    /**
     * root被夹在两颗子树的中间，也就是在nodes列表的中间,是否能够一下子确定下来哪个是根节点与列表的长度有关
     * 当是偶数的时候,除于2的就行
     * 否则的话还需要借助前序遍历和后续遍历中的任意一个序列的信息来完成
     * 在这里我们选用一个BFS的方式来进行确定一棵二叉树
     * @return
     */
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.isEmpty()){
            return null;
        }
        String[] nodes = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        queue.offer(root);
        for(int i = 1;i<nodes.length;){
            TreeNode head = queue.poll();
            String left = nodes[i++];
            if(!NULL.equals(left)){
                head.left = new TreeNode(Integer.parseInt(left));
                queue.offer(head.left);
            }else{
                head.left = null;
            }
            String right = nodes[i++];
            if(!NULL.equals(right)){
                head.right = new TreeNode(Integer.parseInt(right));
                queue.offer(head.right);
            }else{
                head.right =null;
            }
        }
        return root;
    }


}
